import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class Backtracking {
    final int N;
    final int start;//出发点
    int[][] D;//用于存储两个城市之间的距离
    boolean done[];
    LinkedList<Integer> steps=new LinkedList<>();
    int nowTake=0;//当前路径已经花费
    LinkedList<Integer> minSteps=new LinkedList<>();//当前走过的最小花费的路径
    int minTake=Integer.MAX_VALUE;//当前走过的路径的最小花费
    Backtracking(int D[][],int N,int start){
        done = new boolean[N];
        this.start=start;
        this.D=D;
        this.N=N;
    }
    int randomStep(boolean done1[]){
//        if (steps.size()==N) return start;//是否是叶节点
        boolean flag=true;//当前节点下是否搜索完了
        for (boolean b:done1){
            if(!b){
                flag=false;
                break;
            }
        }
        if (flag) return -1;//搜索完了
        while (true){
            int nextStep=(int)(Math.random()*N);
            if (!done1[nextStep]) return nextStep;
        }
    }
    public List<Integer> run(){
        int step=start;
//        steps.push(step);
        boolean done1[]=new boolean[N];
        fact(step);
        Collections.reverse(minSteps);//反转一下
        return minSteps;
    }

    private void fact(int step) {
//        if (nowTake>minTake) return;剪枝内容
        done[step]=true;
        boolean done1[] = done.clone();
        done1[step]=true;//记录现在的位置
        steps.push(step);
        if (steps.size()==N){
            if (nowTake<minTake) {
                minTake = nowTake+D[step][start];
                minSteps = (LinkedList<Integer>) steps.clone();
            }
            steps.pop();
            done[step]=false;
            return;
        }
        while (true){
            int nextStep=randomStep(done1);//下一步,排除done1中的记录
            if (nextStep==-1) {//找不着更好的，后退
                steps.pop();
                done[step]=false;
                return;
            }
            done1[nextStep]=true;
            nowTake+=D[step][nextStep];
            fact(nextStep);//向前走
            nowTake-=D[step][nextStep];
        }
    }

}
